from pulp import *

# List of all nodes - {s,t}
nodes = ['%s' % i for i in range(27) if not i == 19]

# List of all connections
connections =   { 's':  ['0','1','2','3','4','5'],
                  '0':  ['6','7'],
                  '1':  ['7','8'],
                  '2':  ['3','8','9'],
                  '3':  ['2','9'],
                  '4':  ['9','10'],
                  '5':  ['10'],
                  '6':  ['0','7','18'],
                  '7':  ['0','1','6','8','18'],
                  '8':  ['1','2','7','12'],
                  '9':  ['2','3','4','11','12'],
                  '10': ['4','5','11'],
                  '11': ['9','10','13','14'],
                  '12': ['8','9','15','17','23'],
                  '13': ['11','14','15'],
                  '14': ['11','13','15','19'],
                  '15': ['12','13','14','16','24','19'],
                  '16': ['15','24','25','19'],
                  '17': ['12','18','23'],
                  '18': ['6','7','17','20','21'],
                  '19': ['14','15','16'],
                  '20': ['18','22','26'],
                  '21': ['18','22','23'],
                  '22': ['20','21','23','24','25','26'],
                  '23': ['12','17','21','22','24'],
                  '24': ['15','16','22','23'],
                  '25': ['16','22','26'],
                  '26': ['20','22','25']
                }
# List of all capacities from node n1 to node n2, n1_n2
# Bidirection is taken care of in the LP variable creation
capacities =    { 's_0':   None,
                  's_1':   None,
                  's_2':   None,
                  's_3':   None,
                  's_4':   None,
                  's_5':   None,
                  '0_6':   20,
                  '0_7':   10,
                  '1_7':   10,
                  '1_8':   10,
                  '2_3':   15,
                  '2_8':   40,
                  '2_9':   25,
                  '3_9':   5,
                  '4_9':   10,
                  '4_10':  10,
                  '5_10':  10,
                  '6_7':   10,
                  '6_18':  20,
                  '7_8':   10,
                  '7_18':  10,
                  '8_12':  10,
                  '9_11':  15,
                  '9_12':  20,
                  '10_11': 20,
                  '11_13': 20,
                  '11_14': 20,
                  '12_15': 30,
                  '12_17': 30,
                  '12_23': 10,
                  '13_14': 10,
                  '13_15': 40, 
                  '14_15': 10,
                  '14_19': 30,
                  '15_16': 10,
                  '15_19': 30,
                  '15_24': 10,
                  '16_19': 50,
                  '16_24': 200,
                  '16_25': 200,
                  '17_18': 30,
                  '17_23': 10,
                  '18_20': 10,
                  '18_21': 10,
                  '20_22': 50,
                  '20_26': 50,
                  '21_22': 50,
                  '21_23': 50,
                  '22_23': 50,
                  '22_24': 50,
                  '22_25': 50,
                  '22_26': 50,
                  '23_24': 50,
                  '25_26': 50
                }

# List of all edges (v,u) exepct edges from sink to nodes
edges = []
sink = '19'
for c in connections:
    l = connections.get(c)
    for i in l:
        if not c == sink:
            edges.append( (c, "%s" % i) )

# Creates the boundless edge variables as integers
vars = LpVariable.dicts("Edge",edges,None,None,LpInteger)

# Creates the upper and lower bounds on the variables
for e in edges:
    c = capacities.get("%s_%s" % (e[0], e[1]))
    if not c:
        # if not in capacities switch direction
        c = capacities.get("%s_%s" % (e[1], e[0]))
    vars[e].bounds(0,c)
    

# The LP problem
prob = LpProblem("Max Flow Problem", LpMaximize)

# The objective function
prob += lpSum([vars[e] for e in edges if e[0] == 's']), "Maximum flow"

# The flow conservation constraints
for n in nodes:
    prob += lpSum([vars[(i,j)] for (i,j) in edges if j == n]) >= lpSum([vars[(i,j)] for (i,j) in edges if i == n]), "Positive flow conservation in node: %s" % n
    prob += lpSum([vars[(i,j)] for (i,j) in edges if j == n]) <= lpSum([vars[(i,j)] for (i,j) in edges if i == n]), "Negative flow conservation in node: %s" % n

# The problem is solved using PuLP's choice of Solver
prob.solve()

# The status of the solution is printed to the screen
print "Status:", LpStatus[prob.status]

# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
    print v.name, "=", v.varValue

# The optimised objective function value is printed to the screen    
print "Maximum network flow = ", value(prob.objective)
